{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Operations to Reinitialize a Permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reinitializePermutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #还原排列的最少操作步数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个偶数 <code>n</code>​​​​​​ ，已知存在一个长度为 <code>n</code> 的排列 <code>perm</code> ，其中 <code>perm[i] == i</code>​（下标 <strong>从 0 开始</strong> 计数）。</p>\n",
    "\n",
    "<p>一步操作中，你将创建一个新数组 <code>arr</code> ，对于每个 <code>i</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>i % 2 == 0</code> ，那么 <code>arr[i] = perm[i / 2]</code></li>\n",
    "\t<li>如果 <code>i % 2 == 1</code> ，那么 <code>arr[i] = perm[n / 2 + (i - 1) / 2]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>然后将 <code>arr</code>​​ 赋值​​给 <code>perm</code> 。</p>\n",
    "\n",
    "<p>要想使 <code>perm</code> 回到排列初始值，至少需要执行多少步操作？返回最小的 <strong>非零</strong> 操作步数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>最初，perm = [0,1]\n",
    "第 1 步操作后，perm = [0,1]\n",
    "所以，仅需执行 1 步操作</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>最初，perm = [0,1,2,3]\n",
    "第 1 步操作后，perm = [0,2,1,3]\n",
    "第 2 步操作后，perm = [0,1,2,3]\n",
    "所以，仅需执行 2 步操作</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= n <= 1000</code></li>\n",
    "\t<li><code>n</code>​​​​​​ 是一个偶数</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-operations-to-reinitialize-a-permutation](https://leetcode.cn/problems/minimum-number-of-operations-to-reinitialize-a-permutation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-operations-to-reinitialize-a-permutation](https://leetcode.cn/problems/minimum-number-of-operations-to-reinitialize-a-permutation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '4', '6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        step, pow2 = 1, 2\n",
    "        while pow2 != 1:\n",
    "            step += 1\n",
    "            pow2 = pow2 * 2 % (n - 1)\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        n -= 1\n",
    "        step, pow2 = 1, 2\n",
    "        while pow2 != 1:\n",
    "            step += 1\n",
    "            pow2 = pow2 * 2 % n\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        def operate( l:list ,n):\n",
    "            res = []\n",
    "            for i in range( len(l) ):\n",
    "                if i%2 == 0:\n",
    "                    res.append(l[int(i/2)])\n",
    "                else:\n",
    "                    res.append( l[ int( n/2 + (i-1)/2 ) ] )\n",
    "            return res\n",
    "        res = 1\n",
    "        orin_arr = list(range(n) )\n",
    "        change_arr = operate(orin_arr, n )\n",
    "        while change_arr[1] != orin_arr[1]:\n",
    "            change_arr = operate(change_arr ,n )\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        ans, i = 0, 1\n",
    "        while 1:\n",
    "            ans += 1\n",
    "            if i < n >> 1:\n",
    "                i <<= 1\n",
    "            else:\n",
    "                i = (i - (n >> 1)) << 1 | 1\n",
    "            if i == 1:\n",
    "                return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        n -= 1\n",
    "        step, pow2 = 1, 2\n",
    "        while pow2 != 1:\n",
    "            step += 1\n",
    "            pow2 = pow2 * 2 % n\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        ans, i = 0, 1\n",
    "        while 1:\n",
    "            ans += 1\n",
    "            if i < n//2:\n",
    "                i=i*2\n",
    "            else:\n",
    "                i = (i-n//2)*2+1\n",
    "            if i == 1:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        p=list(range(0,n))\n",
    "        p1=list(range(0,n))\n",
    "        y=0\n",
    "        a=[]\n",
    "        l=0\n",
    "        while p!=p1 or y==0:\n",
    "            y+=1\n",
    "            l+=1\n",
    "            a=[]\n",
    "            for i in range(n):\n",
    "                e=int(i/2)\n",
    "                r=int(n/2)+int((i-1)/2)\n",
    "                if i%2==0:\n",
    "                    a.append(p[e])\n",
    "                else:\n",
    "                    a.append(p[r])\n",
    "            p=a\n",
    "        return l\n",
    "          \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        step, pow2 = 1, 2\n",
    "        while pow2 != 1:\n",
    "            step += 1\n",
    "            pow2 = pow2 * 2 % (n - 1)\n",
    "        return step\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        t = n // 2\n",
    "        steps = [*chain(range(1, t), range(-t+1, 0))]\n",
    "        cur = 0\n",
    "        ans = 1\n",
    "        cur += steps[cur]\n",
    "        while cur != 0:\n",
    "            cur += steps[cur]\n",
    "            ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        if n==2:\n",
    "            return 1\n",
    "        ans=1\n",
    "        a=n/2\n",
    "        while a!=1:\n",
    "            if a%2==0:\n",
    "                a=a/2\n",
    "            else:\n",
    "                a=n/2+(a-1)/2\n",
    "            ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        # 模拟\n",
    "        def turn(arr):\n",
    "            n = len(arr)\n",
    "            tmp = [0]*n\n",
    "            for i in range(n):\n",
    "                if i%2==0:\n",
    "                    b = int(i/2)\n",
    "                    tmp[i] = arr[b]\n",
    "                else:\n",
    "                    b = int(n/2+(i-1)/2)\n",
    "                    tmp[i] = arr[b]\n",
    "            return tmp\n",
    "        \n",
    "        perm = [i for i in range(n)]\n",
    "        tm = turn(perm)\n",
    "        cnt = 1\n",
    "        while tm != perm:\n",
    "            tm = turn(tm)\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        prev = list(range(n))\n",
    "        count = 0\n",
    "        while True:\n",
    "            count += 1\n",
    "            match = 0\n",
    "            curr = [-1] * n\n",
    "            for i in range(n):\n",
    "                if i % 2 == 0:\n",
    "                    curr[i] = prev[i // 2]\n",
    "                else:\n",
    "                    curr[i] = prev[n // 2 + (i - 1) // 2]\n",
    "                if curr[i] == i:\n",
    "                    match += 1\n",
    "            if match == n:\n",
    "                break\n",
    "            prev = curr\n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        perm = list(range(n))\n",
    "        arr = [0] * n\n",
    "        while 1:\n",
    "            for i in range(n):\n",
    "                if i % 2: arr[i] = perm[n//2+(i-1)//2]\n",
    "                else: arr[i] = perm[i//2]\n",
    "            ans += 1\n",
    "            i = 0\n",
    "            while i < n and arr[i] == i: i += 1\n",
    "            if i == n: return ans\n",
    "            perm = arr[:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        t = list(range(n))\n",
    "        arr = [0] * n\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                arr[i] = t[i // 2]\n",
    "            else:\n",
    "                arr[i] = t[n // 2 + (i - 1) // 2]\n",
    "        \n",
    "        perm = arr\n",
    "        ans = 1\n",
    "        while perm != t:\n",
    "            arr = [0] * n\n",
    "            for i in range(n):\n",
    "                if i % 2 == 0:\n",
    "                    arr[i] = perm[i // 2]\n",
    "                else:\n",
    "                    arr[i] = perm[n // 2 + (i - 1) // 2]\n",
    "            perm = arr\n",
    "            ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        t = list(range(n))\n",
    "        perm = list(range(n))\n",
    "        ans = 0\n",
    "        while perm != t or not ans:\n",
    "            arr = [0] * n\n",
    "            for i in range(n):\n",
    "                if i % 2 == 0:\n",
    "                    arr[i] = perm[i // 2]\n",
    "                else:\n",
    "                    arr[i] = perm[n // 2 + (i - 1) // 2]\n",
    "            perm = arr\n",
    "            ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        ans=1\n",
    "        a=n/2\n",
    "        while a!=1:\n",
    "            if a%2==0:\n",
    "                a=a/2\n",
    "            else:\n",
    "                a=n/2+(a-1)/2\n",
    "            ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        perm = list(range(n))\n",
    "        target = perm.copy()\n",
    "        step = 0\n",
    "        while True:\n",
    "            step += 1\n",
    "            perm = [perm[n // 2 + (i - 1) // 2] if i % 2 else perm[i // 2] for i in range(n)]\n",
    "            if perm == target:\n",
    "                return step\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        perm = [i for i in range(0, n)]\n",
    "        permInit = [i for i in range(0, n)]\n",
    "\n",
    "        cnt = 1\n",
    "        perm = [i//2 if i % 2 == 0 else n//2 + (i-1)//2 for i in perm]\n",
    "        while perm != permInit:\n",
    "            perm = [i//2 if i % 2 == 0 else n//2 + (i-1)//2 for i in perm]\n",
    "            cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        cur_idx = 1\n",
    "        step = 0\n",
    "        while cur_idx!=1 or step==0:\n",
    "            if cur_idx>=n//2:\n",
    "                cur_idx = (cur_idx-n//2)*2+1\n",
    "            else:\n",
    "                cur_idx *= 2\n",
    "            step +=  1\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        # 模拟\n",
    "        # def turn(arr):\n",
    "        #     n = len(arr)\n",
    "        #     tmp = [0]*n\n",
    "        #     for i in range(n):\n",
    "        #         if i%2==0:\n",
    "        #             b = int(i/2)\n",
    "        #             tmp[i] = arr[b]\n",
    "        #         else:\n",
    "        #             b = int(n/2+(i-1)/2)\n",
    "        #             tmp[i] = arr[b]\n",
    "        #     return tmp\n",
    "        \n",
    "        # perm = [i for i in range(n)]\n",
    "        # tm = turn(perm)\n",
    "        # cnt = 1\n",
    "        # while tm != perm:\n",
    "        #     tm = turn(tm)\n",
    "        #     cnt += 1\n",
    "        # return cnt\n",
    "\n",
    "\n",
    "        count = 1\n",
    "        origin = [i for i in range(n)]\n",
    "        arr = origin[::2]+origin[1::2]\n",
    "        while origin != arr:\n",
    "            arr = arr[::2]+arr[1::2]\n",
    "            count += 1\n",
    "        return count\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        perm = list(range(n))\n",
    "        arr = [0] * n\n",
    "        while True:\n",
    "            cnt += 1\n",
    "            for i in range(n):\n",
    "                if i & 1 == 0:\n",
    "                    arr[i] = perm[i // 2]\n",
    "                else:\n",
    "                    arr[i] = perm[n // 2 + (i - 1) // 2]\n",
    "            if all(arr[i] == i for i in range(n)):\n",
    "                return cnt\n",
    "            for i in range(n):\n",
    "                perm[i] = arr[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        result = 1\n",
    "        i = n//2\n",
    "        while(i != 1):\n",
    "            if(i % 2 == 0):\n",
    "                i = i // 2\n",
    "            else:\n",
    "                i = n // 2 + (i - 1) // 2\n",
    "            result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        perm_0 = [i for i in range(n)]\n",
    "        perm = perm_0.copy()\n",
    "        arr = [0 for i in range(n)]\n",
    "        step = 0\n",
    "        run = True\n",
    "        while run:\n",
    "            for i in range(n):\n",
    "                if i%2==0:\n",
    "                    arr[i] = perm[int(i/2)]\n",
    "                else:\n",
    "                    arr[i] = perm[int(n/2 +(i-1)/2)]\n",
    "            perm = arr.copy()\n",
    "            if perm == perm_0:\n",
    "                run = False\n",
    "            step+=1\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        \n",
    "        k, pow2 = 1, 2\n",
    "        while pow2 != 1:\n",
    "            k += 1\n",
    "            pow2 = pow2 * 2 % (n - 1)\n",
    "        \n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        perm = [i for i in range(n)]\n",
    "        init_perm = perm.copy()\n",
    "       \n",
    "        count = 0\n",
    "\n",
    "        while True:\n",
    "            tmp = []\n",
    "\n",
    "            for index, value in enumerate(init_perm):\n",
    "                if index % 2 == 0:\n",
    "                    m = int(index / 2)\n",
    "                    tmp.append(init_perm[m])\n",
    "                    \n",
    "                elif index % 2 == 1:\n",
    "                    tmp.append(init_perm[int(n / 2 + (index - 1) / 2)])\n",
    "\n",
    "            count += 1\n",
    "            \n",
    "            if tmp == perm:\n",
    "                break\n",
    "\n",
    "            init_perm[:] = tmp\n",
    "            \n",
    "        return count\n",
    "\n",
    "  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        step = 1\n",
    "        perm = list(range(n))\n",
    "        lst = perm.copy()\n",
    "        while True:\n",
    "            perm = [perm[n // 2 + (i - 1) // 2] if i % 2 else perm[i // 2] for i in range(n)]\n",
    "\n",
    "            if perm == lst:\n",
    "                return step\n",
    "            else:\n",
    "                step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        if n==2:\n",
    "            return 1\n",
    "        a=[1,1]\n",
    "        ans=1\n",
    "        a[1]=n/2\n",
    "        while a[0]!=a[1]:\n",
    "            if a[1]%2==0:\n",
    "                a[1]=a[1]/2\n",
    "            else:\n",
    "                a[1]=n/2+(a[1]-1)/2\n",
    "            ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        step, pow2 = 1, 2\n",
    "        while pow2 != 1:\n",
    "            step += 1\n",
    "            pow2 = pow2 * 2 % (n - 1)\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        if n == 2: return 1\n",
    "        ans = 1\n",
    "        n //= 2\n",
    "        x = 2\n",
    "        while x != 1:\n",
    "            x = x * 2 if x < n else 1 + (x - n) * 2\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        result = 1\n",
    "        i = n//2\n",
    "        while(i != 1):\n",
    "            if(i % 2 == 0):\n",
    "                i = i // 2\n",
    "            else:\n",
    "                i = n // 2 + (i - 1) // 2\n",
    "            result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        perm = [i for i in range(n)]\n",
    "        target = perm.copy()\n",
    "        step = 0\n",
    "        while True:\n",
    "            step += 1\n",
    "            perm = [perm[n // 2 + (i - 1) // 2] if i % 2 == 1 else perm[i // 2] for i in range(n)]\n",
    "            if perm == target:\n",
    "                return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        step = 0\n",
    "        perm = list(range(n))\n",
    "        m = n // 2\n",
    "        lst = perm.copy()\n",
    "        while True:\n",
    "            step += 1\n",
    "            perm = [perm[m + (i - 1) // 2] if i % 2 else perm[i // 2] for i in range(n)]\n",
    "\n",
    "            if perm == lst:\n",
    "                return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        step = 0\n",
    "        perm = list(range(n))\n",
    "        m = n // 2\n",
    "        lst = perm.copy()\n",
    "        while True:\n",
    "            step += 1\n",
    "            perm = [perm[m + (i - 1) // 2] if i % 2 else perm[i // 2] for i in range(n)]\n",
    "\n",
    "            if perm == lst:\n",
    "                return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reinitializePermutation(self, n: int) -> int:\r\n",
    "        lt = [i for i in range(n)]\r\n",
    "        cy = lt.copy()\r\n",
    "        cnt = 0\r\n",
    "        while True:\r\n",
    "            cnt += 1\r\n",
    "            lt = [lt[i//2] if i%2==0 else lt[n//2+(i-1)//2] for i in range(n)]\r\n",
    "            if lt == cy:\r\n",
    "                return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        begin=list(range(n))\n",
    "        perm=begin.copy()\n",
    "        count=0\n",
    "        while True:\n",
    "            arr=[perm[i//2] if i%2==0 else perm[n // 2 + (i - 1) // 2]  for i in range(n)]\n",
    "            count+=1\n",
    "            perm=arr\n",
    "            if begin==perm:\n",
    "                break\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 模拟\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        perm = list(range(n))\n",
    "        target = perm.copy()\n",
    "        step = 0\n",
    "        while True:\n",
    "            step += 1\n",
    "            perm = [perm[n // 2 + (i - 1) // 2] if i % 2 else perm[i // 2] for i in range(n)]\n",
    "            if perm == target:\n",
    "                return step\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        visit = [0]*n\n",
    "        for i in range(n):\n",
    "            if visit[i]:\n",
    "                continue\n",
    "            lst = []\n",
    "            x = i\n",
    "            while not visit[x]:\n",
    "                visit[x] = 1\n",
    "                lst.append(x)\n",
    "                if x %2 == 0:\n",
    "                    x //= 2\n",
    "                else:\n",
    "                    x = n//2 + (x-1)//2\n",
    "                \n",
    "            if len(lst) > ans:\n",
    "                ans = len(lst)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        a = []\n",
    "        for i in range(1, n + 1):\n",
    "            a.append(str(i))\n",
    "        tar = ''.join(a)\n",
    "        ans = 0\n",
    "        while True:\n",
    "            ans += 1\n",
    "            perm = [0] * n\n",
    "            for i in range(n):\n",
    "                if i & 1:\n",
    "                    perm[i] = a[n // 2 + (i - 1) // 2]\n",
    "                else:\n",
    "                    perm[i] = a[i // 2]\n",
    "            if ''.join(perm) == tar:\n",
    "                return ans\n",
    "            a = perm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        count = 1\n",
    "        pow2 = 2\n",
    "        while count == 0 or pow2 != 1:\n",
    "            count += 1\n",
    "            pow2 = pow2 * 2 % (n - 1)\n",
    "        return count "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        a=0\n",
    "        perm=[i for i in range(n)]\n",
    "        b=perm[:]\n",
    "        arr=[0]*n\n",
    "        while arr != b:\n",
    "            a+=1\n",
    "            for i in range(n):\n",
    "                if i%2==0:\n",
    "                    arr[i] = perm[i // 2]\n",
    "                else:\n",
    "                    arr[i] = perm[n // 2 + (i - 1) // 2]\n",
    "            perm[:] = arr\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "                \n",
    "                perm = [i for i in range(n)]\n",
    "                t = perm.copy();c = 0\n",
    "                while 1:\n",
    "                    arr = [] \n",
    "                    c += 1\n",
    "                    for i in range(n):\n",
    "                        if i&1:\n",
    "                            arr.append(perm[n // 2 + (i - 1) // 2])\n",
    "                        else:\n",
    "                            arr.append(perm[i//2])\n",
    "                    perm = arr\n",
    "                    if perm == t:\n",
    "                        return c\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        p = [i for i in range(n)]\n",
    "\n",
    "        def fun(l):\n",
    "            t = l.copy()\n",
    "            for i in range(n):\n",
    "                if i % 2:   t[i] = l[n // 2 + (i - 1) // 2]\n",
    "                else:       t[i] = l[i // 2]\n",
    "            return t\n",
    "\n",
    "        t = fun(p); ans = 1\n",
    "        while t != p:\n",
    "            ans += 1\n",
    "            t = fun(t)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "        perm = list(range(n))\n",
    "        target = perm.copy()\n",
    "        step = 0\n",
    "        while True:\n",
    "            step += 1\n",
    "            perm = [perm[n // 2 + (i - 1) // 2] if i % 2 else perm[i // 2] for i in range(n)]\n",
    "            if perm == target:\n",
    "                return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reinitializePermutation(self, n: int) -> int:\n",
    "      perm = [i for i in range(n)]\n",
    "      arr = [0 for _ in range(n)]\n",
    "      res = 0\n",
    "      while arr != [i for i in range(n)]:\n",
    "        for i in range(n):\n",
    "          if i%2 == 0:\n",
    "            arr[i] = perm[i//2]\n",
    "          else:\n",
    "            arr[i] = perm[n//2+(i-1)//2]\n",
    "        # print(arr)\n",
    "        res += 1\n",
    "        perm = arr.copy()\n",
    "      return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
